了解区块链的基本（第一部分）：拜占庭容错(Byzantine Fault Tolerance)

区块链本质上是去中心化的系统，由不同的成员计算机组成，这些成员的行为取决于它们的动机和它们可以获得的信息。

每当一个新的交易被广播到网络中时，节点就可以选择将该交易包含在它们的帐簿副本中，或者忽略它。当组成网络的大多数成员统一意见时，达到了共识。

分布式计算和多代理系统中的一个基本问题是，在存在许多出错的进程的情况下，实现整个系统的可靠性。这通常需要进程来在计算过程中需要的一些数据值上保持一致性。

这些进程被描述为共识。

• 当成员决定不遵守规则和篡改他的帐簿状态时会发生什么？

• 当这些成员是网络的一大部分但不是多数时会发生什么？

为了创建一个安全的共识协议，它必须是容错的。

首先，我们会简单讨论一下不可解的两个将军问题（Two Generals Problem）。然后，我们会引申到拜占庭将军问题和讨论在分布式的去中心化系统中的拜占庭容错。最后，我们会讨论这些与区块链空间如何相关。

两个将军问题

这个问题（1975首次发行，1978年被命名）描述了两个将军在攻击同一个敌人的场景。将军1号被认为是领导，而另一个被认为是跟随者。每个将军的军队都无法仅靠自己的力量成功打败敌军，所以他们需要合作并同一时间发起攻击。这看起来是一个简单的情况，但有一点要注意：

为了两军的沟通和决定作战时间，将军1号必须要派遣一个信使穿过敌人的营地去把攻击时间告诉将军2号。但是，信使可能会被敌人抓住因而信息无法传到友军。那会导致将军1号发起攻击时，将军2号和他的军队还呆在原地。

即使第一条信息传到了，将军2号也需要确认（ACK，注意和TCP三次握手的相似之处）他收到了信息，所以他要派遣一个信使回去，因此重复上一个信使可能被抓的情况。这会延伸到无限的ACK，两位将军将无法达成一致。

没有任何办法可以保证第二个要求，那就是每个将军都要确保对方同意了攻击计划。两个将军都总会怀疑他们最后的信使是否能到达。

因为信使无法到达的可能性总是大于0，所以将军们永远无法以100%的自信达成共识。

两个将军问题已被证实无解。

拜占庭将军问题

于1982年由Lamport、Shostak和Pease着名描述，是一个带反转的广义版本的两个将军问题。它描绘了同一个场景，但两个以上的将军需要对攻打他们共同敌人的时间作出同意。增加的一层复杂性就是，其中一个或几个将军有可能是叛徒，意味着他们可以对他们的选择撒谎（比如他们同意在0900发起攻击但实际上他们不）。

两个将军问题中领导者－跟随者的关系变成了指挥官－中尉的组合。为了在这里达成共识，指挥官和每个中尉必须就同一个决定达成一致（为了简单，只有攻击或撤退）。

拜占庭将军问题，第三页

除了IC2.之外，有趣的事，如果指挥官是叛徒，还是必须达成共识。结果，所有的中尉成为了多数票。

在这种情况下达成共识的算法是基于一个中尉所观察到的大多数决策的价值。

定理：对于任意m，如果有多于3m的将军和至多m个叛徒，算法OM(m)达到共识。

这说明只要2/3的成员是诚实的，算法就能达到共识。如果叛徒多于1/3，无法达到共识，这些军队无法协调他们的攻击，敌军胜利。

m = 0 -> 没有叛徒，每个中尉都服从｜m > 0 -> 每个中尉的最终选择来自于大多数中尉的选择

一个从中尉2号角度来看的示意图应该看得更清楚——C是指挥官，L{i}是中尉i号：

OM(1)：中尉3号是叛徒－从L2角度来看

步骤：

1. 指挥官派v去找所有中尉

2. L1派v去找L2｜L3派x去找L2

3. L2 <- 大多数(v,v,x) == v

最后的决定是来自L1、L2、L3的大多数票，因此达成了共识。

要记得，重要的是大多数中尉要选同一个决策，哪一个并不重要。

让我们来检验指挥官是叛徒的情况：

OM(1): 指挥官是叛徒

步骤：

1. 指挥官派x、y、z去分别找L1、L2、L3

2. L1派x去找L2、L3｜L2派y去找L1、L3｜L3派z去找L1、L2

3. L1 <- 大多数(x,y,z)｜L2 <- 大多数(x,y,z)｜L3 <- 大多数(x,y,z)

他们的数值都一样所以达成了共识。这里花点时间来想一下，即使x,y,z各不相同，所有三个中尉的大多数(x,y,z)的值是相同的。在x,y,z全部不一样的情况时，我们可以假设他们采取默认选项撤退。

要是想了解一个更实用的方法和一个更复杂的7个将军和2个叛徒的例子，我建议你读这篇文章。(http://marknelson.us/2007/07/23/byzantine/)

拜占庭容错

拜占庭容错是一个定义容许属于拜占庭将军问题失败类别的系统的特性。拜占庭故障(Byzantine Failure)是失效模式中最困难级别的。这意味着没有任何限制，也不会假设节点可以具有的行为类型（例如，一个节点可以生成任何类型的任意数据时假装成一个诚实的成员）。

拜占庭故障是最严重最难处理的。在飞机发动机系统、核电站和几乎所有行为取决于大量传感器结果的系统都需要拜占庭容错。就连SpaceX都曾考虑过它为系统的潜在需求。

前面提到的算法，只要叛徒的数量不超过将军的三分之一，就是拜占庭容错。其他变形的存在使得解决问题更容易，包括使用数字签名或通过在网络中的对等体之间施加通信限制。

这些和区块链有什么关系？

区块链是不受中央权威管制的去中心化帐簿们。由于存储在这些帐簿中的价值，不良成员有巨大的经济动机去尝试造成故障。所以，拜占庭容错，也就是拜占庭将军问题的解决方案是区块链非常需要的。

在没有BFT的情况下，同行可以传输和发布虚假交易，从而有效地消除了区块链的可靠性。更糟糕的是，没有中央权威来接管和修复损害。

发明比特币时的一个重大突破就是利用“工作证明”(Proof-of-Work)作为拜占庭将军问题的概率解决方案。想了解更多，请参考Satoshi Nakamoto在这封电子邮件(https://www.mail-archive.com/[e-mail]/msg09997.html)中的深入描述。

总结

在这篇文章中，我们讨论了在分布式系统中共识的一些基本概念。

在下一篇文章中，我们将讨论并比较一些在区块链中用于实现拜占庭容错的算法。